package sorting;

import java.util.Arrays;
import java.util.Random;

public class Heap {
	int[] a;
	int size;

	void fixUp(int k) {
		int j;
		while ((j = k >> 1) >= 1) {
			if (a[j] <= a[k])
				break;
			int temp = a[j];
			a[j] = a[k];
			a[k] = temp;
			k = j;
		}
	}

	void fixDown(int k) {
		int j;
		while ((j = k << 1) <= size) {
			if (j + 1 <= size && a[j + 1] <= a[j])
				j++;
			if (a[j] >= a[k])
				break;
			int temp = a[j];
			a[j] = a[k];
			a[k] = temp;
			k = j;
		}
	}

	void heap() {
//		for (int i = 2; i <= size; i++) {
//			fixUp(i);
//		}
		for(int i = size>>1;i>=1;i--){
			fixDown(i);
		}
	}

	void sort() {
		heap();
		while (size >= 2) {
			int temp = a[size];
			a[size] = a[1];
			a[1] = temp;
			size--;
			fixDown(1);
		}
	}

	public static void main(String[] args) {
		Heap m = new Heap();
		m.size = 20;
		m.a = new int[m.size+1];
		Random rand = new Random();
		for(int i = 1;i<=m.size;i++){
			m.a[i] = rand.nextInt(30);
		}
		System.out.println(Arrays.toString(m.a));
		m.sort();
		System.out.println(Arrays.toString(m.a));
	}
}
